public class Search {
    public int search(int[] nums, int target) {
        // leetcode 搜索旋转排序数组
        // https://leetcode.cn/problems/search-in-rotated-sorted-array/description/?envType=study-plan-v2&envId=top-100-liked
        int n = nums.length;
        if (n == 1) return nums[0] == target ? 0 : -1;
        int left = 0, right = n-1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            // 如果相等则直接返回
            if (nums[mid] == target) {
                return mid;
            }
            // mid的左侧或者右侧一定是有序的，然后我们可以根据判断target是否在有序的那一侧

            // 说明左侧是有序的，为什么这里要加等号，因为我们求mid的时候使用的是left+(right-left)/1
            // 那么就可能出现左侧只有一个元素的情况，只有一个元素也可以认为是有序的
            if (nums[0] <= nums[mid]) {
                // 判断target是否在左侧的有序部分
                if (nums[0] <= target && nums[mid] > target) {
                    right = mid - 1;
                }else {
                    left = mid + 1;
                }
            }else {
                // 表示右侧是有序的
                if (nums[mid] < target && nums[n-1] >= target) {
                    left = mid + 1;
                }else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] nums = {3,1};
        Search search = new Search();
        System.out.println(search.search(nums, 1));
    }
}
